#ifdef KITSCHY_DEBUG_MEMORY 
#include "debug_memorymanager.h"
#endif

#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#include <time.h>
#endif
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "math.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "AUfeatureterm.h"
#include "FT_refinement.h"
#include "FT_generalization.h"

#include "entropy.h"

#include "psm.h"


Prediction *eva_LID(FeatureTerm *problem,List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model,int heuristic,int selection_mode,int min_precedents)
{
	Prediction *prediction=0;

	FeatureTerm *justification=0;

	List<FeatureTerm> different_solutions;
	List<FeatureTerm> descriptions,solutions;

	int npaths;
	FeatureTerm **patterns;
	float *patterns_h;
	int *patterns_coverage;
	int selected;
	
	List< List<FeatureTerm> > partitions_a,partitions_b;

	// Compute descriptions and solutions:
	{
		List<FeatureTerm> *l;
		FeatureTerm *c;

		cases->Rewind();
		while(cases->Iterate(c)) {
			l=c->readPath(description_path);
			descriptions.Add(l->ExtractIni());
			delete l;
			l=c->readPath(solution_path);
			solutions.Add(l->ExtractIni());
			delete l;
		} /* while */ 
	}

	// Compute the list of different solutions:
	{
		FeatureTerm *sol;

		solutions.Rewind();
		while(solutions.Iterate(sol)) {
			if (!different_solutions.MemberP(sol)) different_solutions.Add(new FeatureTerm(sol));
		} /* while */ 
	}

	// compute all paths (objects containing a single path with the final value):
	{
		List<Path> paths;
		List< List<FeatureTerm> > values;

		List< List<FeatureTerm> > stack_values;
		List<Path> stack_path;
		List<Symbol> *l;
		List<FeatureTerm> *l2;
		FeatureTerm *ft,*ft2,*ft3;
		Symbol *feature;
		Path *path,*path2;
		List<FeatureTerm> *value,*value2;
		int max_depth=4;

		value=new List<FeatureTerm>;
		value->Add(new FeatureTerm(problem));
		stack_values.Add(value);
		stack_path.Add(new Path);

		/* get all paths: */ 
		while(!stack_values.EmptyP()) {
			value=stack_values.ExtractIni();
			path=stack_path.ExtractIni();

			value->Forward();
			ft=value->GetObj();

			if (path->Length()>=max_depth || ft->leafP()) {
				value2=new List<FeatureTerm> (*value);
				ft2=value2->ExtractIni();
				delete ft2;
				values.Add(value2);
				paths.Add(new Path(*path));
			} else {

				if (ft->isFeatureTerm()) {
					l=ft->getSort()->getFeatures();

					while(!l->EmptyP()) {
						feature=l->ExtractIni();

						ft2=ft->featureValue(feature);
						if (ft2!=0) {
							path2=new Path(*path);
							path2->Add(new Symbol(feature));
							value2=new List<FeatureTerm>(*value);
							value2->Add(ft2);
							stack_values.Add(value2);
							stack_path.Add(path2);
						} /* if */ 

						delete feature;
					} /* while */ 
					delete l;

				} /* if */ 

				if (ft->isSet()) {
					l2=ft->set_values();

					while(!l2->EmptyP()) {
						ft2=l2->ExtractIni();

						path2=new Path(*path);
						value2=new List<FeatureTerm>(*value);
						ft3=value2->Extract();
						delete ft3;
						value2->Add(ft2);
						stack_values.Add(value2);
						stack_path.Add(path2);
					} /* while */ 
					delete l2;
				} /* if */ 

			} /* if */ 

			delete value;
			delete path;
		} /* while */ 

		npaths=paths.Length();
/*
		{
			char *s;
			printf("Paths (%i):\n",paths.Length());
			paths.Rewind();
			values.Rewind();
			while(paths.Iterate(path) && values.Iterate(value)) {
				path->Rewind();
				value->Forward();
				ft=value->GetObj();

				while(path->Iterate(feature)) {
					printf("%s ",feature->get());					
				} // while  

				s=ft->toNiceString();
				printf("[ %s ]\n",s);
				delete []s;
			} // while  
			printf("\n");
		}
*/
		/* construct the patterns representing the paths: */ 
		{
			Sort *sort;
			Symbol *feature;
			FeatureTerm *pattern,*pointer,*ft,*ft2;
			int i=0;

			patterns=new FeatureTerm *[npaths];

			paths.Rewind();
			values.Rewind();
			while(paths.Iterate(path) && values.Iterate(value)) {
				path->Rewind();
				value->Rewind();

				sort=problem->getSort();
				pattern=new FeatureTerm((Symbol *)0,sort,0);
				pointer=pattern;

				while(path->Iterate(feature) &&
					  value->Iterate(ft)) {

					if (path->EndP()) {
						pointer->defineFeatureValue(feature,new FeatureTerm(ft));
						pointer=0;
					} else {
						sort=ft->getSort();
						ft2=new FeatureTerm((Symbol *)0,sort,0);
						pointer->defineFeatureValue(feature,ft2);
						pointer=ft2;
					} /* if */ 
					
				} /* while */ 

				patterns[i]=pattern;
				i++;
			} /* while */ 
		}
/*
		{
			int i;
			char *s;

			printf("Patterns (%i):\n",npaths);
			for(i=0;i<npaths;i++) {
				s=patterns[i]->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			} // for  
			printf("\n");
		}
*/

	}

	// start with an empty term:
	justification=new FeatureTerm((Symbol *)0,problem->getSort(),0);

	// LID:
	{
		int i;
		bool terminate=false;

		while(!terminate) {
/*
			{
				char *s;
				FeatureTerm *sol,*sol2;
				List<FeatureTerm> l,l2;
				int count;

				s=justification->toStringNOOS(domain_model);
//				printf("Justification:\n%s\n",s);
//				AW_Entity::write_debug_report("Justification:\n%s\n",s);
				delete []s;
//				printf("Precedents: %i\n",descriptions.Length());
//				AW_Entity::write_debug_report("Precedents: %i\n",descriptions.Length());

				l.Instance(different_solutions);
				l2.Instance(solutions);
				while(l.Iterate(sol)) {
					count=0;
					l2.Rewind();
					while(l2.Iterate(sol2)) if (*sol==*sol2) count++;

//					s=sol->toNiceString();
//					printf("%s - %i | ",s,count);
//					AW_Entity::write_debug_report("%s - %i | ",s,count);
//					delete []s;

				} // while  
//				printf("\n");
//				AW_Entity::write_debug_report("\n");
			}
*/
			// compute all the partitions generated by the patterns and its heuristics (binary, by subsumption)
			{
				FeatureTerm *pattern;
				int i;
				float h;

				patterns_h=new float[npaths];
				patterns_coverage=new int[npaths];

				for(i=0;i<npaths;i++) {
					pattern=patterns[i];
					switch(heuristic) {
					case 0:	/* Information Gain: */ 
							h=h_information_gain(&descriptions,&solutions,&different_solutions,pattern,&patterns_coverage[i]);
							break;
					case 1: /* RLDM: */ 
							h=1-h_rldm(&descriptions,&solutions,&different_solutions,pattern,&patterns_coverage[i]);
							break;
					case 2: /* Entropy: */ 
							h=h_entropy(&descriptions,&solutions,&different_solutions,pattern,&patterns_coverage[i]);
							break;
					default:
							patterns_coverage[i]=0;
							h=0;
							break;
					} /* switch */ 	
					patterns_h[i]=h;
				} /* for */ 
			}

			// sort patterns:
			{
				int j;
				int i_tmp;
				float f_tmp;
				FeatureTerm *ft_tmp;

				for(i=0;i<npaths;i++) {
					for(j=0;j<i;j++) {
						if (patterns_h[i]<patterns_h[j]) {
							ft_tmp=patterns[i];
							patterns[i]=patterns[j];
							patterns[j]=ft_tmp;

							f_tmp=patterns_h[i];
							patterns_h[i]=patterns_h[j];
							patterns_h[j]=f_tmp;

							i_tmp=patterns_coverage[i];
							patterns_coverage[i]=patterns_coverage[j];
							patterns_coverage[j]=i_tmp;
						} // if  
					} // for  
				} // for  
			}

/*
//			printf("%i\n",npaths);
			AW_Entity::write_debug_report("%i\n",npaths);
			for(i=0;i<npaths;i++) {
				char *str;
				str=patterns[i]->toStringNOOS(domain_model);
//				printf("%f [%i]\n",1-patterns_h[i],patterns_coverage[i]);
				AW_Entity::write_debug_report("%f [%i] %s\n",1-patterns_h[i],patterns_coverage[i],str);
				delete []str;
				{
					FeatureTerm *d;
					descriptions.Rewind();
					while(descriptions.Iterate(d)) {
						if (patterns[i]->subsumes(d)) {
							AW_Entity::write_debug_report("<%s>",d->getName()->get());
						} // if  
					} // while  
					AW_Entity::write_debug_report("\n");
				}
				{
					FeatureTerm *d;
					descriptions.Rewind();
					while(descriptions.Iterate(d)) {
						if (!patterns[i]->subsumes(d)) {
							AW_Entity::write_debug_report("not <%s>",d->getName()->get());
						} // if  
					} // while  
					AW_Entity::write_debug_report("\n");
				}
			} // for  
*/

			// choose a pattern:
			switch(selection_mode) {
				case 0:/* MAXIMUM: */ 
					{
						int i;
						float maximum=patterns_h[0];
						selected=0;

						for(i=1;i<npaths;i++) {
							if (patterns_h[i]>maximum || (patterns_h[i]==maximum && patterns_coverage[i]>patterns_coverage[selected])) {
								maximum=patterns_h[i];
								selected=i;
							} /* if */ 
						} /* for */  
					}
					break;
				case 1:/* RANDOM: */ 
					selected=rand()%npaths;
					break;
				case 2:/* RANDOM PONDERATED: */ 
					{
						int i;
						float h_sum=0;
						float tmp,accum;

//						printf("{ 0");
						for(i=0;i<npaths;i++) {
							h_sum+=patterns_h[i];
//							printf(" - %g",h_sum);
						} /* if */ 
						tmp=(float(rand())*h_sum)/float(RAND_MAX);

						selected=-1;
						accum=0;
						for(i=0;selected==-1 && i<npaths;i++) {
							if (accum+patterns_h[i]>tmp) selected=i;
							accum+=patterns_h[i];
						} /* for */ 

//						printf(" } -> %g -> %i\n",tmp,selected);

						if (selected==-1) selected=rand()%npaths;
					}
					break;
				case 3:/* MINIMUM: */ 
					{
						int i;
						float minimum=patterns_h[0];
						selected=0;

						for(i=1;i<npaths;i++) {
							if (patterns_h[i]<minimum || (patterns_h[i]==minimum && patterns_coverage[i]>patterns_coverage[selected])) {
								minimum=patterns_h[i];
								selected=i;
							} /* if */ 
						} /* for */  
					}
					break;

				default:
					selected=0;
					break;
			} /* while */ 

			// Apply pattern:
			if (patterns_coverage[selected]>0) {
				// Filter precedents:
				{
					List<FeatureTerm> to_delete_d,to_delete_s;
					FeatureTerm *des,*sol,*pattern;

					pattern=patterns[selected];

					descriptions.Rewind();
					solutions.Rewind();
					while(descriptions.Iterate(des) && solutions.Iterate(sol)) {
						if (!pattern->subsumes(des)) {
							to_delete_d.Add(des);
							to_delete_s.Add(sol);
						} /* if */ 
					} /* while */ 

					while(!to_delete_d.EmptyP()) {
						des=to_delete_d.ExtractIni();
						descriptions.DeleteElement(des);
						delete des;
						sol=to_delete_s.ExtractIni();
						solutions.DeleteElement(sol);
						delete sol;
					} /* while */ 
				}

				// Recompute de list of different solutions:
				{
					FeatureTerm *sol;

					different_solutions.Delete();

					solutions.Rewind();
					while(solutions.Iterate(sol)) {
						if (!different_solutions.MemberP(sol)) different_solutions.Add(new FeatureTerm(sol));
					} /* while */ 

					if (different_solutions.Length()==1) terminate=true;
				}

				// Expand justification:
				{
					FeatureTerm *pointer1,*pointer2;
					FeatureTerm *ft1,*ft2,*ft;
					Symbol *feature;
					Sort *sort;
					List<Symbol> *l;

					pointer1=justification;
					pointer2=patterns[selected];

					while(pointer2!=0) {
						sort=pointer2->getSort();
						l=sort->getFeatures();
						while(!l->EmptyP()) {
							feature=l->ExtractIni();
							ft1=pointer1->featureValueQuick(feature);
							ft2=pointer2->featureValueQuick(feature);

							if (ft2!=0) {
								l->Delete();
								if (ft1==0) {
									pointer1->defineFeatureValue(feature,ft2->clone(domain_model));
									pointer2=0;
								} else {
									if (ft2->leafP()) {
										if (ft1->equivalents(ft2)) {
											pointer2=0;
										} else {
											ft1=new FeatureTerm(ft1);
											pointer1->removeFeatureValue(feature);
											
											ft=FeatureTerm::SetFeatureTerm((Symbol *)0);
											ft->addSetValue(ft1);
											ft->addSetValue(ft2->clone(domain_model));

											pointer1->defineFeatureValue(feature,ft);
											pointer2=0;
										} /* if */ 
									} else {

										if (domain_model->MemberP(ft1)) {
											ft1=new FeatureTerm(ft1);
											pointer1->removeFeatureValue(feature);
											
											ft=FeatureTerm::SetFeatureTerm((Symbol *)0);
											ft->addSetValue(ft1);
											ft->addSetValue(ft2->clone(domain_model));

											pointer1->defineFeatureValue(feature,ft);
											pointer2=0;
										} else {
											if (ft2->getSort()->isSubsort(ft1->getSort())) {
												pointer1=ft1;
												pointer2=ft2;
											} else {
												printf("Case not considered 2! ---------------------------\n");
												
												/* Specialize sort if possible, otherwise create a set: */ 
												/* ... */ 

												pointer2=0;
											} /* if */ 


										} /* if */ 									
									} /* if */ 
								} /* if */ 
							} /* if */ 
							delete feature;
						} /* while */ 
						delete l;
					} /* while */ 

/*
					{
						char *s;
						s=justification->toStringNOOS(domain_model);
						printf("Justification Expanded:\n%s\n",s);
						delete []s;
					}									
*/
				}

				// Remove invalid patterns:
				{
					int j;

					for(i=0;i<npaths;i++) {
						if (patterns_coverage[i]==0 || patterns[i]->subsumes(justification)) {
							delete patterns[i];
							npaths--;
							for(j=i;j<npaths;j++) {
								patterns[j]=patterns[j+1];
								patterns_coverage[j]=patterns_coverage[j+1];
							} /* for */ 
							patterns[npaths]=0;
							i--;
						} /* if */ 
					} /* for */ 
				}

				if (npaths==0) terminate=true;

			} else {
				terminate=true;
			} /* if */ 

			delete []patterns_coverage;
			delete []patterns_h;
		} /* while */ 
	}

	// compute final solution:
	prediction=new Prediction(new FeatureTerm(problem));

	{
		int i;
		List<FeatureTerm> l;
		FeatureTerm *solution;
		int *distribution=new int[different_solutions.Length()];

		for(i=0;i<different_solutions.Length();i++) distribution[i]=0;

		l.Instance(solutions);
		while(l.Iterate(solution)) {
			distribution[different_solutions.Position(solution)]++;
		} /* while */ 

		for(i=0;i<different_solutions.Length();i++) {
			if (distribution[i]>0) {
				prediction->justifications.Add(new FeatureTerm(justification));
				prediction->solutions.Add(new FeatureTerm(different_solutions[i]));
				prediction->support.Add(new int(distribution[i]));		
			} /* if */ 
		} /* for */ 

		delete []distribution;
	} /* if */ 

	{
		int i;

		for(i=0;i<npaths;i++) {
			delete patterns[i];
			patterns[i]=0;
		} /* for */ 
		delete []patterns;

		delete justification;
	}

	return prediction;
} /* eva_LID */ 



